﻿// 0728train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <unordered_set>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <limits.h>

using namespace std;


/*
 给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。
这里的 遵循 指完全匹配，
例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。
示例1:
输入: pattern = "abba", s = "dog cat cat dog"
输出: true
示例 2:
输入:pattern = "abba", s = "dog cat cat fish"
输出: false
示例 3:
输入: pattern = "aaaa", s = "dog cat cat dog"
输出: false 
 */

string GetStringKey(string oh_str)
{
    unordered_map<char, int>oh_map;
    vector<int>oh_vec;

    int count = 1;

    for (auto&oh_char:oh_str)
    {
	    if (oh_map.count(oh_char))
	    {
            oh_vec.push_back(oh_map[oh_char]);
	    }
        else
        {
            oh_map[oh_char] = count;
            oh_vec.push_back(count);
            count += 1;
        }
    }

    string result;
    for (auto&num:oh_vec)
    {
        result += to_string(num);
    }
    return result;
	//GetStringKey
}


string GetStrVecKey(vector<string>str_vec)
{
    unordered_map<string, int>oh_map;
    vector<int>oh_vec;

    int count = 1;

    for (auto&str:str_vec)
    {
	    if (oh_map.count(str))
	    {
            oh_vec.push_back(oh_map[str]);
	    }
        else
        {
            oh_map[str] = count;
            oh_vec.push_back(count);
            count += 1;
        }
        //for------
    }

    string result;
    for (auto& num : oh_vec)
    {
        result += to_string(num);
    }
    return result;
    //GetStrVecKey
}

bool IsSamePattern(string pattern, string s)
{
    string pattern_code = GetStringKey(pattern);

    vector<string>str_vec;
    stringstream oh_stream(s);
    string token;

    while (oh_stream>>token)
    {
        str_vec.push_back(token);
    }

    string str_code = GetStrVecKey(str_vec);

    if (pattern_code==str_code)
    {
        return true;
    }

    return false;
    //IsSamePattern
}


/*
 
 总格数是count，每回合可能连续跳的步教都放在数组steps中，
 请问数组中是否有一种步数的组合，两个回合跳到最后一格?
 如果有，请输出索引和最小的步数组合

注意：
- 数组中的步数可以重复，但数组中的元素不能重复使用。
- 提供的数据保证存在满足题目要求的组合，且索引和最小的步数组合是唯一的

输入描述
第一行输入为每回合可能连续跳的步数，它是整数数组类型。
第二行输入为房子总格数count，它是int整数类型。

输出描述
返回索引和最小的满足要求的步数组合(顺序保持steps中原有顺序)


[1,4,5,2]
7
[5,2]


[-1,2,4,9,6]
8
[-1,9]

只有当两两索引和，小于全局索引和，更新

 */

void solve01(vector<int>num_vec, int target)
{
    //目标：num_vec中的元素凑出target

    unordered_map<int, int>oh_map;

    vector<int>result_vec(2);

    int min_sum_index = 2 * num_vec.size();

    for (int i=0; i<num_vec.size();i++)
    {
        int curr_num = num_vec[i];

        if (oh_map.count(curr_num))
        {
            int prev_index = oh_map[curr_num];
            int prev_num = num_vec[prev_index];

            if (i + prev_index < min_sum_index)
            {
                min_sum_index = i + prev_index;
                result_vec[0] = prev_num;
                result_vec[1] = curr_num;
            }
     
        }
        else
        {
            int next_num = target - curr_num;

            oh_map[next_num] = i;
        }

        //for-------
    }

    cout << '[';
    for (int i=0; i<result_vec.size();i++)
    {
	    if (i!=result_vec.size()-1)
	    {
            cout << result_vec[i] << ',';
	    }
        else
        {
            cout << result_vec[i];
        }
    }
    cout << ']';
    //------
}

/*
 N 个特性（F1, F2, ..., FN）需要进行覆盖测试，
 每个特性都被评估了对应的优先级，特性使用其 ID 作为下标进行标识。
设计了 M 个测试用例（T1, T2, ..., TN ），每个用例对应了一个覆盖特性的集合，
测试用例使用其 ID 作为下标进行标识，测试用例的优先级定义为其覆盖的特性的优先级之和。
在开展测试之前，需要制定测试用例的执行顺序，
规则为：优先级大的用例先执行，如果存在优先级相同的用例，用例 ID 小的先执行。

输入描述
第一行输入为 N 和 M ，N表示特性的数量，M表示测试用例的数量，0＜N<=100 ，0＜M<=100 
之后 N 行表示特性 ID=1 到特性 ID=N 的优先级。
再接下来 M 行表示测试用例 ID=1 到测试用例 ID=M 关联的特性的 ID 的列表。

输出描述
按照执行顺序（优先级从大到小）输出测试用例的 ID，每行一个 ID。
测试用例覆盖的 ID 不重复。

5个特性，4个测试用例
输入
5 4
1
1
2
3
5
1 2 3
1 4
3 4 5
2 3 4

输出
3
4
1
2

说明
测试用例的优先级计算如下：
T1=Pf1+Pf2+Pf3=1+1+2=4
T2=Pf1+Pf4=1+3=4
T3=Pf3+Pf4+Pf5=2+3+5=10
T4=Pf2+Pf3+Pf4=1+2+3=6

 */
struct PNode
{
    int id, weight;
    PNode() = default;
    PNode(int id, int weight) :id(id), weight(weight) {};
};

bool ComparePNode(PNode node_a, PNode node_b)
{
	if (node_a.weight == node_b.weight)
	{
        return node_a.id < node_b.id;
	}
    return node_a.weight > node_b.weight;
}

void solve02(vector<int>&num_vec, vector<vector<int>>&index_total_vec)
{
    vector<PNode>priority_vec;
    
    for (int i=0;i< index_total_vec.size();i++)
    {
        int curr_sum = 0;

        vector<int>index_vec = index_total_vec[i];

        for (auto&index : index_vec)
        {
            curr_sum += num_vec[index-1];
        }
        PNode p_node(i+1, curr_sum);
        priority_vec.push_back(p_node);
       //for------
    }
    sort(priority_vec.begin(), priority_vec.end(), ComparePNode);

    for (auto&item:priority_vec)
    {
        cout << item.id << endl;
    }

    //solve02
    //------
}



/*
 题目描述
给定一段"密文"字符串s，
其中字符都是经过"密码本"映射的，现需要将"密文"解密并且输出。
映射的规则 ："a-i"分别用"1-9"表示，"j-z" 分别用"10*-26*"表示
约束：映射始终唯一


输入描述
“密文”字符串

输出描述
明文字符串

补充说明
翻译后的文本的长度在100以内

输入
20*19*20*
输出
tst

 */
unordered_map<string,string>GetMap()
{
    unordered_map<string, string>oh_map;
    int front_count = 9;

    for (int i=0; i<front_count;i++)
    {
        string oh_str_1;
        char curr_char = 'a' + i;
        oh_str_1 += curr_char;
        oh_map[to_string(i+1)] = oh_str_1;
    }

    //"j-z" 分别用"10*-26*"
    int end_count = 17;
    for (int i = 0; i < end_count; i++)
    {
        string oh_str_1;
        char curr_char = 'j' + i;
        oh_str_1 += curr_char;
        oh_map[to_string(10 + i)+"*"] = oh_str_1;
    }
    //for (auto&item:oh_map)
    //{
    //    cout << item.first << ' ' << item.second<<endl;
    //}

    return oh_map;

}

bool isDigital(char oh_char)
{
    return oh_char >= '0' && oh_char <= '9';
}

void solve03(string oh_str)
{

    unordered_map<string, string>oh_map = GetMap();
    string result;

    string curr_str;
    //第一个char进来，map取值，如果取不到，再下一个char
    //取到了就往result上面拼，清空curr_str
    for (int i=0;i<oh_str.size();i++)
    {
        char curr_char = oh_str[i];
        int curr_num;
        if (isDigital(curr_char))
        {
            curr_num = curr_char - '0';

	        if (i+2<oh_str.size() && oh_str[i+2]=='*')
	        {
                int next_num = oh_str[i + 1] - '0';
                curr_num = curr_num * 10 + next_num;
                i+=2;
	        }
            if (curr_num > 9) curr_str = to_string(curr_num) + "*";
            else curr_str = to_string(curr_num);

            //cout << "curr_str " << curr_str;
        }
        
        if (oh_map.count(curr_str))
        {
            result += oh_map[curr_str];
            curr_str = "";
        }
    }
    
    cout << result;
	//solve03
    //------
}


int main()
{
	{
        //string oh_str;
        //cin >> oh_str;
        string oh_str = "12320*12319*20*";
        //12320*12319*20*
        solve03(oh_str);
        //GetMap();
        return 0;
	}


	{
        int num_vec_size, index_vec_size;
        cin >> num_vec_size >> index_vec_size;
        vector<int>num_vec(num_vec_size);
        vector<vector<int>>index_total_vec(index_vec_size);

        for (int i=0; i<num_vec_size;i++)
        {
            cin >> num_vec[i];
        }

        cin.ignore();

        //for (auto&num:num_vec)
        //{
        //    cout << num << ' ';
        //}
        for (int i=0;i<index_vec_size;i++)
        {
            string input;
            getline(cin, input);
            stringstream oh_sstream(input);
            vector<int>index_vec;

            string token;
            while (oh_sstream>>token)
            {
                index_vec.push_back(stoi(token));
            }
            index_total_vec[i] = index_vec;
        }

        //5 4
        //1
        //1
        //2
        //3
        //5
        //1 2 3
        //1 4
        //3 4 5
        //2 3 4
        //vector<int>num_vec = {1,1,2,3,5};
        //vector<int>index_vec1 = { 1,2,3 };
        //vector<int>index_vec2 = { 1,4 };
        //vector<int>index_vec3 = { 3,4,5 };
        //vector<int>index_vec4 = { 2,3,4 };
        //vector<vector<int>>index_vec = { index_vec1,index_vec2,index_vec3,index_vec4 };

        solve02(num_vec, index_total_vec);

        return 0;
	}

	{
        //[1,4,5,2] 7 [5,2]
        //[-1,2 4,9,6] 8 [-1,9]
        //target = 9
        //nums = [1, 5, 6, 3, 8]
        vector<int>num_vec = { 1, 5, 6, 3, 8 };
        int target = 9;

        //solve01(num_vec, target);
        //cout << num_vec;

        //string input;
        //getline(cin, input);

        //input = input.substr(1, input.size() - 2);
        //stringstream oh_sstream(input);

        //vector<int>num_vec;
        //string token;
        //while (getline(oh_sstream, token, ','))
        //{
        //    num_vec.push_back(stoi(token));
        //}

        //int target;
        //cin >> target;

        solve01(num_vec, target);

        return 0;
	}


    //pattern = "abba", s = "dog cat cat dog" 1
    //pattern = "abba", s = "dog cat cat fish" 0
    //pattern = "aaaa", s = "dog cat cat dog" 0

    string pattern = "aaaa", s = "dog cat cat dog";

    cout << IsSamePattern(pattern, s);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
